#include <stdio.h>
#include <string.h>

/*
 * 贪婪算法
 *
 *	贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。
 *
 *	贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。
 *
 *	必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性
 *
 *	（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
 *
 *	对所采用的贪心策略一定要仔细分析其是否满足无后效性。
 *
 *
 */

#define W  150

struct object
{
    int weight;
    int price;
    int status;
};

struct tag_knapsack_problem
{
    struct object objs[7];
    int total_c;
};

void print_result(struct object *objs)
{
    printf("result = %d %d %d\n", objs->weight, objs->price, objs->status);
}

int choose_func1(struct object * objs, int c)
{
    int index = -1;
    int mp = 0;
    int i;

    for (i = 0; i < 7; i++) {
        if ((objs[i].status == 0) && (objs[i].price > mp)) {
            mp = objs[i].price;
            printf("mp = %d\n", mp);
            index = i;
//             printf("index = %d ", index);
        }
    }

    return index;
}

void greedy_algo(struct tag_knapsack_problem * problem, int (*sp_func)(struct object * objs, int c))
{
    int idx;
    int ntc = 0;

    while ((idx = sp_func(problem->objs, problem->total_c - ntc)) != -1) {
//        printf("idx = %d\n", idx);
        if ((ntc + problem->objs[idx].weight) <= problem->total_c) {
            problem->objs[idx].status = 1;
            ntc += problem->objs[idx].weight;
        }
        else {
            /* can't select this wupin, make a falg after reselect. */
            problem->objs[idx].status = 2;
        }
    }

    print_result(problem->objs);
}

void tanlan_bag()
{
    int w[7] = {35, 30, 60, 50, 40, 10, 25};
    int p[7] = {10, 40, 30, 50, 35, 40, 30};
    struct tag_knapsack_problem problem = {
        .objs[0] = {35, 10, 0},
        .objs[1] = {30, 40, 0},
        .objs[2] = {60, 30, 0},
        .objs[3] = {50, 50, 0},
        .objs[4] = {40, 35, 0},
        .objs[5] = {10, 40, 0},
        .objs[6] = {25, 30, 0},
        .total_c = 150,
    };

    greedy_algo(&problem, choose_func1);
}

void main()
{
    tanlan_bag();
}
